1. The Field of the Invention
The present invention generally relates to the field of digital imaging of multimedia data. More particularly, the invention relates to embedding a sufficiently robust watermark into the image data that can withstand lossy compression schemes without degrading the digital watermark.
2. Present State of the Art
The number of applications that use digital storage and transmission is increasing at a rapid rate. Specifically, types of digital data include digital audio, digital images and digital video, which may be largely electronically distributed over ubiquitous public networks such as cable and telephone infrastructures. Additionally, digital data may be physically exchanged and replicated into exact duplicates of the original.
The proliferation of digital media, e.g., audio, image and video, creates property concerns relating to intellectual property rights, e.g., copyrights. Traditional cryptographic techniques have provided one level of protection by allowing decryption of the encrypted data to be performed only by decryption key holders. However, conventional cryptography provides little protection against data piracy, i.e., unauthorized reproduction of decrypted digital data, since decrypted digital data may be easily replicated and distributed. Such schemes provide insufficient protection against unauthorized reproduction of information and the inability to determine the source or origin of unauthorized duplicates.
It is known in the prior art to provide a xe2x80x9cdigital watermarkxe2x80x9d on a document to address this problem. Traditional digital watermarks on a data file or document may be perceptible and even visible or may be sufficiently embedded within the digital data so as to be imperceptible to those perceiving the digital data. Such digital watermarks remain present within the data even after processing such as a decryption procedure. While visible or humanly perceivable digital watermarks may provide apparent identification of the incorporating entity, such as a copyright owner, noticeable digital watermarks are considered unacceptable for aesthetically integrous media, e.g., imaging and audio data.
Imperceptible watermarks are comprised of an identification code that is permanently embedded within the digital data and may contain specific information such as the identity of the purchaser of a particular copy of the digital data, e.g., audio (speech and music), images (photographic and graphics) and video (movies).
There are techniques that have been proposed for watermarking digital data. In U.S. Pat. No. 5,464,997 to Barton, a method and apparatus is disclosed for basic authentication of a digital block such as an image carrying authentication information provided by the user embedded into the digital block of data. A digital signature comprised of a reduced representation of the digital block of data is embedded by replacing predetermined bits within the digital block of data. The authentication process is performed in reverse order so as to expose the embedded digital signature, thereby authenticating the integrity of the digital block of data. It should be pointed out that such an implementation while adequate for digital data transmission and storage techniques that do not impose compression techniques, are wholly inoperative in modern communication channels that employ sophisticated modulation techniques and other lossy compression methods. While it is possible to employ techniques such as those that use the least significant bits (LSBs) of the image data to conceal or embed the digital watermark, such approaches are obviously not sufficiently robust for enduring lossy compression processes as lossy compression techniques tend to randomize the LSBs. Furthermore, employing the most significant bits of the data image renders the digital watermark perceptible and therefore unacceptable or undesirable for aesthetically demanding forms of digital data. Additionally, employing a frequency transformation followed by embedding the digital watermark in the high frequency bands is also insufficiently robust since elementary lowpass filtering results in the decimation of the digital watermark. Conversely, placing the digital watermark in the low frequency components causes the digital watermark to become perceptible and therefore aesthetically unacceptable. Therefore, it should be apparent that the objectives of creating an imperceptible digital watermark that is additionally sufficiently robust to lossy image processing, e.g,, compression and rescaling, are in direct conflict. That is to say, if the digital watermark is sufficiently robust to lossy imaging processing operations, the digital watermark becomes perceptually significant and therefore unacceptable. Conversely, embedding the digital watermark so as to be imperceptible results in an inadequately robust digital watermark.
It is known that orthogonal transforms e.g., Discreet Cosine Transform (DCT) and Discreet Fourier Transform (DFT), can be used to perform digital watermarking in the transform domain as taught in Cox et al., Secure Spread Spectrum Watermarking for Images, Audio and Video, Proceedings of the 1996 International Conference on Image Processing, Vol. III, pp. 243-246, 1996. In that particular public description, the authors propose inserting a watermark into the spectral components of the digital data using techniques analogous to spread spectrum communications, i.e., hiding a narrow band signal in a wide band channel which is represented by the digital data. However, in such DCT-based approaches, spectral energy is concentrated which facilitates data compression, but becomes disastrous for retaining the integrity of the digital watermark.
In such DCT-based approaches, the low-frequency components are employed, but the mean-value coefficient is excluded. Such an implementation suggests that the DCT-based approaches are not systematic. Such approaches were studied and proposed by Cox et al. due to the popularity of DCT in the industry. Therefore, orthogonal transforms such as the DCT or the DFT are good choices for compression, but are less than desirable choices for digital watermarking. The fundamental disadvantage of such techniques result from the fact that such techniques offer energy compaction and are therefore not sufficiently adequate choices for a spread spectrum-based algorithm.
Thus, it appears that there exists no digital watermarking scheme that is capable of embedding an adequately imperceptible digital watermark into a digital data file, wherein the digital watermark is sufficiently robust to withstand lossy image processing operations (e.g., compression and resealing), while remaining detectable following such degradation processing. There also does not exist any digital watermarking technique that is sufficiently strongly resistant to unauthorized detection and decoding, even by individuals cognizant of the present watermarking techniques. Finally, there exists no digital watermarking technique that may be applied to all media types, e.g., audio, images, video, graphics and text (when represented as an image), that may be universally applied.
It is an object of the invention to provide a method for watermarking digital data in such a manner as to cause the digital watermark to remain resilient throughout lossy compression processes.
It is a further object of the present invention to provide a method for designating and determining the origin of digital data which may be subjected to lossy compression techniques through the use of a digital watermark.
It is a further object of the present invention to provide a method for spreading a digital watermark across digital data such that when a portion of the frequencies of the digital data are compressed and thereby disposed, the digital watermark remains intact and discernable.
Yet another object of the present invention is to provide a method for determining the origin of a particular copy of digital data through the use of a digital watermark adequately embedded within the digital data such that lossy compression techniques do not obscure or degenerate the digital watermark.
It is yet another object of the present invention to provide a method for determining the legitimacy of a copy of digital data which has a digital watermark embedded thereon.
It is yet another object of the present invention to provide a digital watermark that is imperceptible when embedded within digital data and is thereby aesthetically acceptable for marking digital data, such as images, that dictate imperceptible steganography or embedding of data such as a digital watermark.
It is a further advantage of the present invention to provide a digital watermarking technique that is strongly resistant to unauthorized detection and decoding even to those familiar with the watermarking technique of the present invention.
Yet another advantage of the present invention permits graceful degradation, such as lossy compression, of the digital data having the watermark embedded thereon while retaining the integrity of the watermark following a decompression process.
It is yet another advantage of the present invention to provide a universal watermark that can be applied to a myriad of media types, (e.g., audio, images, video, graphics and text when represented as an image), while being implemented in a practical and efficient implementation that is conducive to computerized processing.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
To achieve the foregoing objects, and in accordance with the invention as embodied and broadly described herein, a method and apparatus for digitally watermarking digital data is presented which is visually imperceptible and strongly resistant to unauthorized detection and decoding. Furthermore, the watermarking technique of the present invention is robust to lossy compression and other image processing operations such as rescaling. The watermarking principle of the present invention is based on wavelet transforms where the coefficients of the filters have binary values, and thus are very attractive for practical realization. These wavelet filters are related to complimentary polynomials, which are also related to multifilter banks. Experimental results have shown that multifilter banks, in addition to scalar filter banks, are advantageous for applications such as that of the present invention.
Those skilled in the art of digital signal processing appreciate that the number of applications that use digital storage and transmission is increasing at a rapid rate. Such applications include digital audio, images and video, transmission of video over public networks (e.g., cable and telephone networks). Therefore, protection of these various forms of digital data are fundamental to securing certain rights, such as intellectual property rights, that enure to the benefit of the right holder. For example, publishers and artisans have long relied upon access control (i.e., physically controlling access) to provide security to their works. Subsequent techniques such as cryptography have provided limited protection against unauthorized reproduction by restricting those individuals that are authorized or retain the decryption algorithm for decrypting their artistic work. However, once the data is decrypted, it is freely copyable without a trace of information describing the origin of the casually protected data. To provide a tag or other identifying information, prior implementations have utilized a digital watermark which was perceptually significant and thereby degraded the aesthetic value of the digital data. Furthermore, attempts to place watermarks throughout digital data have often been destroyed by image processing techniques such as data compression operations. If a watermark is to be robust to lossy image processing operations, it may become perceptually significant unless, as in the present invention, the digital watermark is spread across the digital data.
Those skilled in the art of digital signal processing appreciate the value of transforming spatial data into a transform domain, such as the frequency domain, in which signal processing operations may be performed. One popular transform is the discreet cosine transform (DCT). While a DCT process could be employed for embedding a watermark, the primary disadvantage of the DCT is that it offers energy concentration, as opposed to energy spreading which is necessary for a robust method of embedding a durable watermark. Yet another transform technique appreciated by those of skill in the art is the wavelet transform which, however, also provides energy compaction and even more so than the DCT. Therefore, traditional or regular wavelets, the most prominent of which are the Daubechies wavelets, are less desirable choices for watermarking. Those of skill in the art appreciate that regular wavelets are continuous functions which implies that the impulse responses of the filers which tenerate them are relatively smooth.
While it is not wholly appreciated, there are other types of wavelets, such as non-regular wavelets or wavelets which do not provide continuous functions. Non-regular wavelets have completely contrasting physical properties from regular wavelets. For example, they do not generate multiresolution analysis and although the filter coefficients form orthogonal bases for the Hilbert space in the discrete-time case, non-regular wavelet functions do not form orthogonal bases for the Hilbert space of continuous-time functions. It is known that complimentary polynomials are intimately related to wavelets, and in fact, these complimentary polynomials are highly non-regular wavelets with coefficients having two values, 1 and xe2x88x921. An additional embodiment of the present invention employs complimentary matrix polynomials which are related to multiwavelets.
The present invention employs a suggested watermarking algorithm wherein the digital data or digital signal is partitioned into blocks, which are not necessarily of the same length, but are partitioned such that the amplitude of the signal within a block does not change or vary significantly. A subsequent step of the watermarking algorithm of the present invention is to generate a subband tree that is either a pruned or a complete subband tree through which the wavelet transform may be performed. While a complete subband tree may be employed, additional security is derived by employing uniquely pruned subband trees. The forward orthogonal circular wavelet transform, or alternatively the multiwavelet transform, may be performed such that the filter coefficients have only two values, 1 and xe2x88x921. Additionally, the polyphase components of the filters are complimentary sequences.
The next step of the watermarking algorithm is to insert the watermark by modulating some or all of the wavelet coefficients. Since the wavelets are highly non-regular, this is equivalent to placing the watermark everywhere in the frequency domain. The watermark itself may be a sequence of random numbers or it may be a predetermined sequence such as an ASCII text string. Both imperceptible and perceptible watermarks may be employed as long as the aesthetic qualities of the digital data are not significantly impaired. Following the insertion or overlaying of the digital watermark, the inverse orthogonal circular wavelet transform is performed with the corresponding synthesis filter bank to obtain the watermarked digital data. The watermarked digital data may be compressed, transmitted, filtered or otherwise processed with the watermark remaining discernable and intact.
The algorithm for verifying whether unknown digital data incorporates a specific watermark may be performed by decomposing the digital data into blocks as was performed during the embedding process. Subsequently, the same subband tree as was utilized in the embedding processing, either a complete or pruned subband tree is reconstructed for the wavelet transform. A forward wavelet transform is performed on the unknown or distributed watermarked data to determine the wavelet coefficients. Likewise, a forward wavelet transform is performed on a previously stored copy of the original digital data, also known as the reference data, to determine the wavelet coefficients of the pristine or reference digital data. The wavelet coefficients of both of the forward transformed digital data (unknown data and reference data) are compared to extract a difference which would be representative of any watermark data present within the unknown digital data. The extracted or corrupted difference sequence representing any resident watermark is compared with the watermark or reference watermark stored previously during the embedding process. If the extracted watermark sequence is sufficiently close, (i.e. within a predefined verification threshold), such as if the extracted watermark sequence coincides with more than fifty percent of the reference watermark, then it is concluded that the watermark is present in the unknown data. If the watermark is a random sequence, compared with the reference watermark, then it is determined that either the digital watermark was not present in the unknown data or the unknown data was sufficiently corrupted to make the verification process statistically challenging.
The watermarking technique of the present invention is robust to unauthorized detection, even if an attacker knows the original image and watermarking principle, (i.e., even if the attacker knows that a wavelet transform has been used and the filter coefficients obtained form a complimentary sequences). To achieve success by an attacker, the attacker must find the exact number of filter coefficients and the exact values of these coefficients. Since the number of different complimentary polynomials grows exponentially with their length, such an attack cannot be accomplished in a reasonable amount of time. Secondly, the attacker must also find the exact subband tree that has been employed. Any randomly pruned subband tree can be used in the watermarking process of the present invention. Thirdly, since there are even more complimentary matrix polynomials than scalar complimentary polynomials, one may use multiwavelet transforms to achieve an even higher level of security.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
These and other objects and features of the present invention will become more fully apparent from the following description and appended claims or may be learned by the practice of the invention as set forth hereinafter.